960C - Subsequence Counting - CodeForces Solution


bitmasks constructive algorithms greedy implementation *1700

Please click on ads to support us..

Python Code:

import heapq
def main():
    X,d = [int(i) for i in input().split()]
    X = X
    s = bin(X)[2:]

    ones = s.count('1')
                    res = []
    count = 0
    oneCount = 0
    for i in reversed(range(len(s))):
        if s[i]=='1':
            res.append(count)
            oneCount += 1
        count +=1
    ANS = []
    START = d
        for c in res:
        ANS.extend([str(START) for _ in range(c)])
        START += d
    for i in range(oneCount):
        ANS.append(str(START))
        START += d
    if len(ANS)>10000:
        print(-1)
    else:
        print(len(ANS))
        print(' '.join(ANS))
    return
    
    

if __name__ == "__main__":
    main()

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()

const int MAXN = 5e5+5;
int n = 0, d = 0;
ll akt_val = 0, akt_ile = 0, akt_ilo = 0;
vector<ll> wyn;

void solve()
{
	cin >> n >> d;
	wyn = vector<ll>();

	akt_val = 1;
	while(n > 0)
	{
		akt_ile = 1, akt_ilo = 2;
		while(akt_ilo*2-1 <= n)
		{
			akt_ilo *= 2, ++akt_ile;
		}
		rep(i,akt_ile) wyn.pb(akt_val);
		akt_val += d, n -= akt_ilo-1;
	}

	cout << wyn.size() << '\n';
	for(auto x : wyn) cout << x << ' ';
	cout << '\n';
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}


Comments

Submit
0 Comments
More Questions

1455B - Jumps
1225C - p-binary
1525D - Armchairs
1257A - Two Rival Students
1415A - Prison Break
1271A - Suits
259B - Little Elephant and Magic Square
1389A - LCM Problem
778A - String Game
1382A - Common Subsequence
1512D - Corrupted Array
667B - Coat of Anticubism
284B - Cows and Poker Game
1666D - Deletive Editing
1433D - Districts Connection
2B - The least round way
1324A - Yet Another Tetris Problem
246B - Increase and Decrease
22E - Scheme
1566A - Median Maximization
1278A - Shuffle Hashing
1666F - Fancy Stack
1354A - Alarm Clock
1543B - Customising the Track
1337A - Ichihime and Triangle
1366A - Shovels and Swords
919A - Supermarket
630C - Lucky Numbers
1208B - Uniqueness
1384A - Common Prefixes